struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
};

class Solution
{
public:
    void Transform(TreeNode *cur, TreeNode *&pre)
    {
        if (cur == nullptr)
        {
            return;
        }

        Transform(cur->left, pre);
        cur->left = pre;
        if (pre)
        {
            pre->right = cur;
        }
        pre = cur;
        Transform(cur->right, pre);
    }
    TreeNode *Convert(TreeNode *pRootOfTree)
    {
        TreeNode *pre = nullptr;
        Transform(pRootOfTree, pre);

        TreeNode *head = pRootOfTree;
        while (head && head->left)
        {
            head = head->left;
        }
        return head;
    }
};